#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include "strmap.h"

//Wrapper para alocação de memória. Termina o programa e
//exibe mensagem de erro caso a alocação não tenha sido feita com sucesso.
void* allocate(int bytes);

//Verifica se a palavra é palíndromo.
int palindromo(char* palavra);

//Retorna a soma dos códigos ASCII de cada letra da palavra.
int word_to_ascii(char* palavra);

//Algoritmo do crivo de Erastótenes. Retorna o vetor de primos em **primos
void erastotenes(int** primos, int* num_primos, int max_primo);

//Busca binária (utilizada na verificação de se um número é primo)
int busca_binaria(int* vetor, int tamanho, int chave);

//Somente os seguintes caracteres são considerados
//como separadores, respectivamente: todos, de frase e de palavra.
//Sendo assim, frases são consideradas todo conjunto de caracteres
//separado por algum dos caracteres em SEPARADORES_FRASE. Palavras
//são consideradas todo conjunto de caracteres separado por algum dos
//caracteres em SEPARADORES.
char SEPARADORES[]         = " \n\r\t.,:;\"!?-()'";
char SEPARADORES_FRASE[]   = "\n\r\t.!?";
char SEPARADORES_PALAVRA[] = " ,:;\"-()'";

int main(int argc, char* argv[])
{
   struct timeval ti, tf;
   long int sec, usec;
   
   //Início da contagem de tempo
   gettimeofday(&ti, NULL);

   int mode; //Modo de execução (1 - menor texto, 2 - maior texto)
   int file_size;
   int i, num_palavras, num_palindromos, num_frases, max_ascii, num_primos;
   int *primos;
   int* soma_ascii;
   char *text, *text_buffer, *aux;
   char buffer[2046];
   char **palavras, **frases;
   FILE *fp;
   StrMap *sm;
   
   mode = atoi(argv[1]);
   
   //Determina o tamanho do arquivo
   fp = fopen(argv[2], "rb");
   fseek(fp, 0L, SEEK_END);
   file_size = ftell(fp);
   rewind(fp);

   //Lê o texto em memória como uma única string
   text_buffer = (char*) allocate((file_size + 1) * sizeof(char));
   if(fread(text_buffer, 1, file_size, fp) != file_size)
   {
      printf("Erro na leitura do arquivo.\n");
      exit(0);
   }
   text_buffer[file_size] = '\0';
   
   //Converte o texto para lowercase
   for(i = 0; i < file_size; i++)
      text_buffer[i] = tolower(text_buffer[i]);

   //Copia o buffer para um outro (que será modificado no processo)
   text = (char*) allocate((file_size + 1) * sizeof(char));
   strcpy(text, text_buffer);
   
   palavras = (char**) allocate(file_size * sizeof(char*));
   palavras[0] = strtok(text, SEPARADORES);
   //Guarda as posições de cada palavra ocorrente no texto
   for(i = 0; palavras[i] != NULL; )
      palavras[++i] = strtok(NULL, SEPARADORES);
   num_palavras = i;
   if(mode == 2)
      soma_ascii = (int*) allocate(num_palavras * sizeof(int));
   
   //Verifica cada palavra para a ocorrência de palíndromos
   sm = sm_new(num_palavras);
   printf("Palindromos:\n\n");
   for(i = 0, max_ascii = 0, num_palindromos = 0; i < num_palavras; i++)
      if(palindromo(palavras[i]))
         if(!sm_exists(sm, palavras[i]))
         {
            sm_put(sm, palavras[i], "");

            if(mode == 2)
            {
               soma_ascii[num_palindromos] = word_to_ascii(palavras[i]);
               if(max_ascii < soma_ascii[num_palindromos])
                  max_ascii = soma_ascii[num_palindromos];               
            }
            
            printf("%d: %s\n", ++num_palindromos, palavras[i]);
         }   
   
   //Repete o processo, porém para frases em vez de palavras
   if(mode == 1)
   {
      strcpy(text, text_buffer);  
      frases = palavras;

      frases[0] = strtok(text, SEPARADORES_FRASE);
      for(i = 0; frases[i] != NULL; )
      {
         //printf("%s\n", frases[i]);
         frases[++i] = strtok(NULL, SEPARADORES_FRASE);
      }
      num_frases = i;
      //printf("%d\n", i);

      for(i = 0; i < num_frases; i++)
      {
         aux = strtok(frases[i], SEPARADORES_PALAVRA);
         buffer[0] = '\0';
         while(aux != NULL)
         {
            strcat(buffer, aux);
            aux = strtok(NULL, SEPARADORES_PALAVRA);
         }
         if(palindromo(buffer) && !sm_exists(sm, buffer))
         {
            sm_put(sm, buffer, "");
            printf("%d: %s\n", ++num_palindromos, buffer);
         }
      }
   }
   
   if(mode == 2)
   {
      //Executa o algoritmo do crivo de Erastótenes
      erastotenes(&primos, &num_primos, max_ascii);
      
      printf("\nSomas ASCII primas:\n\n");
      for(i = 0; i < num_palindromos; i++)
         if(busca_binaria(primos, num_primos, soma_ascii[i]))
            printf("%d: %d\n", i+1, soma_ascii[i]);
   }
   printf("\n");

   //Término da contagem de tempo
   gettimeofday(&tf, NULL);
   sec = tf.tv_sec - ti.tv_sec;
   if(tf.tv_usec < ti.tv_usec)
      sec--;
   usec = (tf.tv_usec - ti.tv_usec + 1000000) % 1000000;
   printf("Tempo decorrido: %ld.%06ld s.\n", sec, usec);
   return 0;   
}

//Aloca memoria, finaliza o programa em caso de erro
void* allocate(int bytes)
{
   void *ptr;
   
   ptr = malloc(bytes);
   if(ptr == NULL)
   {
      printf("Erro na alocação de memória.\n");
      exit(0);
   }
   
   return ptr;
}

//Verifica se a palavra é palíndromo 
int palindromo(char* palavra)
{
   int i, len;
   
   len = strlen(palavra);
   
   if(len < 2)
      return 0;
   for(i = 0; i < len/2; i++)
      if(palavra[i] != palavra[len - i - 1])
         return 0;
         
   return 1;
}

//Retorna a soma dos códigos ASCII da palavra
int word_to_ascii(char* palavra)
{
   int i, soma;
   
   soma = 0;
   for(i = 0; palavra[i] != '\0'; i++)
      soma += (int) palavra[i];
   
   return soma;
}

//Algoritmo do crivo de Erastótenes
void erastotenes(int** primos, int* num_primos, int max_primo)
{
   int i, j, np;
   int* crivo;
   
   crivo = (int*) allocate((max_primo + 1) * sizeof(int));
   for(i = 0; i <= max_primo; i++)
      crivo[i] = 1;

   for(i = 2, np = 0; i <= max_primo; i++)
   {
      if(i <= sqrt(max_primo))
         if(crivo[i])
            for(j = 2*i; j <= max_primo; j += i)
               crivo[j] = 0;
      np += crivo[i];
   }

   *num_primos = np;
   *primos = (int*) allocate(np * sizeof(int));
   
   for(i = 2, j = 0; j < np; i++)
      if(crivo[i])
         (*primos)[j++] = i;
         
   return;
}

//Busca binária (utilizada na verificação de se um número é primo)
int busca_binaria(int* vetor, int tamanho, int chave)
{
   int idmin, idmax, idmed, salto;
   
   idmin = 0;
   idmax = tamanho - 1;
   
   while(idmin != idmax)
   {
      idmed = (idmin + idmax) / 2;
      
      if(idmed == idmin || idmed == idmax)
         if(vetor[idmin] == chave || vetor[idmax] == chave)
            return 1;
         else
            return 0;
      
      if(chave > vetor[idmed])
         idmin = idmed;
      else if(chave < vetor[idmed])
            idmax = idmed;
           else
            return 1;
   }
   
   return 0;
}
